The invention relates to apparatus for sorting information records and has applicability to electronic digital computers. More particularly, this invention relates to apparatus having the ability to sort records overlapped with their input to, and output from, the apparatus with no discernible sorting time.
The need for the electronic processing of vast amounts of data has triggered the development of large scale, fast electronic digital computer systems which process these vast amounts of data, in part, by processing sequences of records within the computer. One of the facilities of great importance in such a computer system is a facility for sorting records.
However, conventional sorting has taken undue amounts of time in the scheme of electronic data processing. Typically, the required time to sort N records in a conventional sorter is of the order N log.sub.2 N, which grows much faster than N. This invention, on the other hand, performs sorting overlapped with the input and the output of the records with no discernible sort time; it is regular and modular, and is easily implementable in large scale integration circuitry. It can interface directly with the sources of the records, and free the central processing unit of computer systems to do other tasks.
Accordingly, it is a general object of this invention to provide an apparatus which allows the sorting of information records overlapped with input and output thereof to and from storage.
A more particular object of the invention is to provide apparatus in a digital computer system for sorting records by permuting the order of selected record pairs as the records are being received as an input to, and ejected as an output from, storage devices.